/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-03-31 13:20:56
 * @LastEditors: lily
 * @LastEditTime: 2021-04-13 14:53:58
 */
/*
 * @lc app=leetcode.cn id=22 lang=javascript
 *
 * [22] 括号生成
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */

//  思路：回溯法
//  有约束的选括号：
//  只要 ( 有剩，就可以选 ( 。 (((((这么选，都还不能判定为非法。
//  当剩下的 ) 比 ( 多时，才可以选 ) ，否则 ) 不能选，选了就非法了。
//  描述节点的状态有：当前构建的字符串，和左右括号所剩的数量。
//  https://leetcode-cn.com/problems/generate-parentheses/solution/shou-hua-tu-jie-gua-hao-sheng-cheng-hui-su-suan-fa/

//  复杂度：O(2^{2n}n) O(n)

var generateParenthesis = function (n) {

    let res = []
    //  左右括号所剩的数量，str是当前构建的字符串
    var dfs = (currStr, r, l) => {
        // 字符串构建完成
        if (r === 0 && l === 0) {
            // 加入解集
            res.push(currStr)
            // 结束当前递归分支
            return
        }
        // 只要左括号有剩，就可以选它，然后继续做选择（递归）
        if (l) {
            dfs(currStr + '(', r, l - 1)
        }
        // 右括号比左括号剩的多，才能选右括号
        if (r > l) {
            // 然后继续做选择（递归）
            dfs(currStr + ')', r - 1, l)
        }
    }
    // 递归的入口，剩余数量都是n，初始字符串是空串
    dfs('', n, n)
    return res
};
// @lc code=end

console.log(generateParenthesis(2));